#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void Print(int *a,int size)
{
    for (int i = 0; i < size;i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
void swap(int *a,int* b )
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
/*冒泡排序*/
void BubbleSort(int *a,int size)
{
    
    for (int i = 0; i < size - 1; i++) // 要整理的数的最大个数
    {
        int flag = 0;
        for (int j = 0; j < size - 1 - i; j++) // 单轮冒泡比较的次数
        { 
            if(a[j]>a[j+1])
            {
                flag = 1;
                swap(&a[j], &a[j + 1]);
            }
        }
        if(flag==0)//遍历数列没有任何俩个数需要交换，说明已经有序
        break;
    }
}
/*插入排序*/
void InsertSort(int *a,int size)
{
    for (int i = 0; i < size;i++)//插入的数据个数
    {
        int j = i;
        int temp = a[i];
        for (; j > 0; j--)//i是要插入的数据的下标
        {
            if(temp<a[j-1])
            {
                a[j] = a[j - 1];//比要插入的值大就往后挪
            }
            else
            {
                break;
            }
        }
        a[j] = temp;
    }
}
void ChooseSort(int *a,int size)
{
    
    for (int i = 0; i < size - 1; i++)
    {
        int min = i;
        for (int j = i+1; j < size ;j++)
        {
            if(a[min]>a[j])
            {
                min = j;
            }
        }
        swap(&a[min], &a[i]);
    }
}
//双指针算法
void ChooseSort2(int *a,int size)
{
    
    for (int left = 0,right=size-1; left<right; left++,right--)
    {
        int min = left;
        int max = right;
        for (int i =left ; i <= right; i++)
        {
            if(a[min]>a[i])
            {
                min = i;
            }
            if(a[max]<a[i])
            {
                max= i;
            }
        }
        swap(&a[left], &a[min]);
        //极值在两边
        if(max==left)
        {
            max = min;
        }
        swap(&a[right], &a[max]);
    }
}
//快速排序：双指针  分治  递归
void FastSort(int *a, int start, int end)
{
      //终止条件
    if(start>=end)
        return;
    int left = start;
    int right = end;
    int temp = a[left];
    while(left<right)
    {
        //先从右边动 找比基准值小的数
        while(a[right]>temp&&left<right)
        {
            right--;
        }
        //把右边的值赋给左边的空位
        if(left<right)
        a[left++] = a[right];
        //左边动，找比基准值大的数
        while(a[left]<temp&&left<right)
        {
            left++;
        }
        //把左边的值赋给右边的空位
        if(left<right)
            a[right--] = a[left];
    }
    a[left] = temp;
    //递归函数
    FastSort(a, start, left - 1);
    FastSort(a, right + 1, end);
}
//二分查找
int BinarySerach(int *a,int size,int element)
{
    int left = 0;
    int right = size - 1;
    while(left <= right)
    {
        int mid = left+(right-left)/2;
        //int mid = (left & right) + (left ^ right) >> 1;
        //比中间值小
        if(a[mid]>element)
        {
            //左半边找
            right = mid - 1;
        }
        else if(a[mid]<element)
        {
            //右半边找
            left = mid +1;
        }
        else
        {
            return mid;
        }
    }
    //没找到
    return -1;
}
int main()
{
    int a[5] = {80,11,37,2,12 };
    // srand(time(NULL));
    // for (int i = 0; i < 5;i++)
    // {
    //     a[i] = rand() % 100+1;
    // }
    Print(a, sizeof(a)/sizeof(a[0]));
    FastSort(a, 0,4);
    Print(a, sizeof(a) / sizeof(a[0]));

    printf("找到的下标是：%d\n", BinarySerach(a, 5, 12));
    return 0;
}